import java.util.Stack;

class Solution {
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        //利用栈到节点存储起来
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int size1=stack1.size();
        int size2=stack2.size();
        if(size1>size2){
            int len=size1-size2;
            while(len!=0){
                stack1.pop();
                len--;
            }
        }else{
            int len=size2-size1;
            while(len!=0){
                stack2.pop();
                len--;
            }
        }
        while(stack1.peek()!=stack2.peek()){
            stack1.pop();
            stack2.pop();
        }
        return stack1.peek();
    }
    public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if(root==null||node==null){
            return false;
        }
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean flag1=getPath(root.left,node,stack);
        if(flag1==true){
            return true;
        }
        boolean flag2=getPath(root.right,node,stack);
        if(flag2==true){
            return true;
        }
        stack.pop();
        return false;
    }
    //二叉树的最近公共祖先
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==q||root==p){
            return root;
        }
        TreeNode nodeLeft=lowestCommonAncestor(root.left,p,q);
        TreeNode nodeRight=lowestCommonAncestor(root.right,p,q);
        if(nodeLeft==null){
            return nodeRight;
        }
        if(nodeRight==null){
            return nodeLeft;
        }
        return root;
    }

    public String minNumber(int[] nums) {
            StringBuilder dp=new StringBuilder();
            String [] res=new String[nums.length];
            //转化为字符串
            for(int i=0;i<nums.length;i++){
                res[i]=String.valueOf(nums[i]);
            }
            for(int i=0;i<res.length-1;i++){
                for(int j=0;j<res.length-1;j++){
                    if((res[j+1]+res[j]).compareTo(res[j]+res[j+1])<0){
                        String tmp=res[j];
                        res[j]=res[j+1];
                        res[j+1]=tmp;
                    }
                }
            }
            for(String s:res){
                dp.append(s);
            }
            return dp.toString();
        }
    }